package sort;

import org.junit.Test;

public class MergeSort {
	@Test
	public void fun() {
		int[] a = {0, 23, 47, 81, 95, 7, 14, 39, 55, 62, 74};
		MergeSort(a);
		for(int i : a) {
			System.out.print(i + "\t");
		}
	}
	public void Merge(int[] initList, int[] mergeList, int l, int m, int n) {	
		//	l表示第一个数组下标，m表示最后一个数组下标，result表示新建数组下标
		int i1, i2, result;
		for(i1 = l, i2 = m + 1, result = i1; i1 <= m && i2 <= n; result ++) {
			if(initList[i1] <= initList[i2]) {
				mergeList[result] = initList[i1];
				i1 ++;
			}else {
				mergeList[result] = initList[i2];
				i2 ++;
			}
		}
		System.arraycopy(initList, i1, mergeList, result, m - i1 + 1);
		System.arraycopy(initList, i2, mergeList, result, n - i2 + 1);
	}
	public void MergePass(int[] initList, int[] mergeList, int n, int s) {
		int i;
		for(i = 1; i <= n - 2*s + 1; i += 2*s) {
			Merge(initList, mergeList, i, i + s - 1, i + 2*s - 1);
		}
		
		if((i + s - 1) < n) {
			Merge(initList, mergeList, i, i + s - 1, n);
		}else {
			System.arraycopy(initList, i, mergeList, i, n + 1 - i);
		}
	}
	public void MergeSort(int[] list) {
		int[] newList = new int[list.length];
		for(int i = 1; i < list.length; i *= 2) {
			MergePass(list, newList, list.length - 1, i);
			i *= 2;
			MergePass(newList, list, list.length - 1, i);
		}
	}
}
